package graph.weighted.shortestPath;
/**
 * 
 * @Title: CandyFloyed.java 
 * @Package graph.weighted.shortestPath 
 * @Description: 使用弗洛伊德算法求解最短路径问题
 * @author CandyWall   
 * @date 2021年1月21日 下午10:49:51 
 * @version V1.0
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

import graph.weighted.CandyWeightedGraph;

public class CandyFloyd {
    private CandyWeightedGraph graph;
    private int[][] distances;
    private int[][] paths;
    private boolean hasNegativeLoop; // 是否包含负权环

    public CandyFloyd(CandyWeightedGraph graph) {
        this.graph = graph;
        
        distances = new int[graph.getVertex_num()][graph.getVertex_num()];
        paths = new int[graph.getVertex_num()][graph.getVertex_num()];
        for(int v = 0; v < graph.getVertex_num(); v++) {
            Arrays.fill(distances[v], Integer.MAX_VALUE);
        }
        for(int v = 0; v < graph.getVertex_num(); v++) {
            for(int w = 0; w < graph.getVertex_num(); w++) {
                // 初值为各个边的终点顶点的下标
                paths[v][w] = w;
            }
            distances[v][v] = 0;
            for(int w : graph.adjacentVertexes(v)) {
                distances[v][w] = graph.getWeight(v, w);
            }
        }
        
        floyed();
    }

    private void floyed() {
        for(int t = 0; t < graph.getVertex_num(); t++) {
            for(int v = 0; v < graph.getVertex_num(); v++) {
                for(int w = 0; w < graph.getVertex_num(); w++) {
                    if(distances[v][t] != Integer.MAX_VALUE 
                       && distances[t][w] != Integer.MAX_VALUE 
                       && distances[v][t] + distances[t][w] < distances[v][w]) {
                        distances[v][w] = distances[v][t] + distances[t][w];
                        paths[v][w] = paths[v][t];  // 路径更新看不懂
                    }
                }
            }
        }
        for(int v = 0; v < graph.getVertex_num(); v++) {
            if(distances[v][v] < 0) {
                hasNegativeLoop = true;
            }
        }
    }
    
    public boolean hasNegativeLoop() {
        return hasNegativeLoop;
    }
    
    /**
     * 获取顶点s到顶点t的最短路径长度
     * @return
     */
    public int getShortestPathLength(int s, int t) {
        graph.validateVertex(s);
        graph.validateVertex(t);
        if(isConnectedTo(s, t)) {
            return distances[s][t];
        }
        return -1;
    }
    
    /**
     * 获取顶点s到顶点t的最短路径（具体经过了哪些边）
     * @return
     */
    public ArrayList<Integer> getShortestPath(int s, int t) {
        graph.validateVertex(t);
        ArrayList<Integer> path = new ArrayList<>();
        if(!isConnectedTo(s, t)) {
            return path;
        }
        // 顶点cur为顶点s和顶点t之间的中介点
        int cur = paths[s][t]; 
        path.add(s);
        // 每次循环，找一下顶点cur和顶点t之间是否有中介点
        while(cur != t) {
            path.add(cur); // 输出中介点
            // 找一下顶点cur和顶点t之间的中介点
            cur = paths[cur][t];
        }
        path.add(t);
        // Collections.reverse(path);
        return path;
    }

    private boolean isConnectedTo(int s, int t) {
        graph.validateVertex(s);
        graph.validateVertex(t);
        return distances[s][t] != Integer.MAX_VALUE;
    }
    
    public int[][] getDistances() {
        return distances;
    }

    public int[][] getPaths() {
        return paths;
    }

    public static void main(String[] args) {
        CandyWeightedGraph graph1 = new CandyWeightedGraph("testData/weightedGraph/shortestPath/Floyed/graph1.txt");
        CandyFloyd floyed1 = new CandyFloyd(graph1);
        int[][] dis1 = floyed1.getDistances();
        for(int v = 0; v < graph1.getVertex_num(); v++) {
            for(int w = 0; w < graph1.getVertex_num(); w++) {
                System.out.print(dis1[v][w] + "\t");
            }
            System.out.println();
        }
        int[][] paths1 = floyed1.getPaths();
        for(int v = 0; v < graph1.getVertex_num(); v++) {
            for(int w = 0; w < graph1.getVertex_num(); w++) {
                System.out.print(paths1[v][w] + "\t");
            }
            System.out.println();
        }
        if(!floyed1.hasNegativeLoop()) {
            System.out.println(floyed1.getShortestPathLength(0, 1));
            System.out.println(floyed1.getShortestPath(4, 1));
        } else {
            System.out.println("含有负权环");
        }
        System.out.println("=========================");
        CandyWeightedGraph graph2 = new CandyWeightedGraph("testData/weightedGraph/shortestPath/Floyed/graph3.txt", true);
        CandyFloyd floyed2 = new CandyFloyd(graph2);
        int[][] dis2 = floyed2.getDistances();
        for(int v = 0; v < graph2.getVertex_num(); v++) {
            for(int w = 0; w < graph2.getVertex_num(); w++) {
                System.out.print(dis2[v][w] + "\t");
            }
            System.out.println();
        }
        /*int[][] paths2 = floyed2.getPaths();
        for(int v = 0; v < graph2.getVertex_num(); v++) {
            for(int w = 0; w < graph2.getVertex_num(); w++) {
                System.out.print(paths2[v][w] + "\t");
            }
            System.out.println();
        }*/
        if(!floyed2.hasNegativeLoop()) {
            System.out.println(floyed2.getShortestPathLength(0, 1));
            System.out.println(floyed2.getShortestPath(0, 1));
        } else {
            System.out.println("含有负权环");
        }
    }
}
